問：n個の要素からなる集合の部分集合は全部で2^n個あることを示せ
問：$ n個の要素からなる集合の部分集合は全部で$ 2^{n}個あることを示せ
は～…また問題が生えてきたよ…cFQ2f7LRuLYP.icon
勝手に問題が生えてくる先進的な数学テキストtakker.icon
1. 1個の要素からなる集合の部分集合は？
仮に$ A=\{1\}の場合
部分集合は$ \{1\}, \{\}……一個？2個か
他にも部分集合があるんかな
下記のLinksの中にヒントがhatori.icon
部分集合は$ \{1\}, \{\}……2個か
2. 2個の要素からなる集合の部分集合は？
$ A=\{1, 2\}
部分集合は以下の４つ
$ \{\}空集合
$ \{1\}1のみ
$ \{2\}2のみ
$ \{1,2\}1と2
これも部分集合に入るのか？
部分集合の定義から，A⊂Aは明らかに成り立ちます.一方，A⊂BかつB⊂Aであれば，A=Bが成り立ちます. したがって，A⊂BかつB⊂Aが成り立つことと，A=Bであることは同値です.(p.3)
入るのか…
これ確率で見たやつだな
n個の互いに異なるボールから任意個のボールをとってくるときの総数yosider.icon
3. 3個の要素からなる集合の場合は？
$ A=\{1,2,3\}
部分集合は…8つ
$ \{\}空集合
要素が1個のみ：3つ
$ \{1\}$ \{2\}$ \{3\}
要素が2個：3つ
$ \{1,2\}$ \{2,3\}$ \{1,3\}
要素が3個：1つ
$ \{1,2,3\}
たしかに$ 2^nの形式になっとるな
ここまでのあらすじ
table:練習問題
部分集合の数
1 2 2^1
2 4 2^2
3 8 2^3
...
n 2^n(?)
案1：1のとき2、2のとき4、3のとき8になります。これはよく見ると$ 2^nの形になってます。だからそうなります！！！！
だめそう
すべての事例についていちいち例示しないといけなくなる
案2：$ \sout{nCr}$ _{n}\mathrm{C}_{r}を使おう
やや入力が面倒なのですが$ {}_{n}C_{r}または$ {}_{n}\mathrm{C}_{r}とした方が誤解の恐れが少ないと思いますhatori.icon
$ nCr=n \times C \times rにみえる
$ \binom{n}{r}や小さめに表示される$ \tbinom{n}{r}という書き方もあります
なるほど、下付きで表現するんですねcFQ2f7LRuLYP.icon
直そう。中に線引くのはどうやってやるんだったかな
$ \sout{abc}[$ \sout{abc}]
$ _{n}\mathrm{C}_{r}[$ _{n}C_{r}]
おおー書けた
……といいつつこれなんだったか忘れたんだよなあ
数学ガールの秘密ノートをよんでみよ
場合の数の話を買ってなかったことが判明。なんともはや
第3章 代数にこの書き方の秘密がのっているぞ
さて，異なるn個のものからm個を選び出す場合(選び出すだけで，並べたりはしない)の数を，$ _{n}\mathrm{C}_{m} と書こう。$ _{n}\mathrm{C}_{m} はどんな式になるだろうか?(p.30)
前段階で$ _{n}\mathrm{P}_{m}、順列の計算をしている $ _{n}\mathrm{P}_{m}と$ _{n}\mathrm{C}_{m}の差異は何か？
$ _{n}\mathrm{P}_{m}は「異なるn個からm個選んで並べる」場合の数
$ _{n}\mathrm{P}_{m}=n\times(n-1)\times\cdots\times(n-m+1)
これが3個の内から3個並べる場合だとどうなるか？
$ _{3}\mathrm{P}_{3}=3\times2\times1=6
すなわち$ 3!になるのか
$ _{n}\mathrm{C}_{m}は「異なるn個からm個選ぶ」場合の数
abcdの4つの文字から3つの文字を抜き出す。このときパターンはいくつあるか？
1. abc
2. abd
3. acb
4. acd
5. adb
6. adc
7. bac
8. bad
9. bca
10. bcd
11. bda
12. bdc
13. cab
14. cad
15. cba
16. cbd
17. cda
18. cdb
19. dab
20. dac
21. dba
22. dbc
23. dca
24. dcb
この24通りのうち組み合わせが同じものがある
table:組み合わせ
1 abc acb bac bca cab cba
2 abd adb bad bda dab dba
3 acd adc cad cda dac dca
4 bcd bdc cbd cdb dbc dcb
したがって「abcdの4つの文字から3つの文字を抜き出す組み合わせ」は4通りだといえる
5枚から3枚を選ぶ組み合わせの総数は、次のように考えるとよいでしょう。
・まず、順列と同様に「順序を考えて」数える。
・重複して数えてしまった分(重複度)で割り算する。
プログラマの数学p.134
今回の場合は
1. 「順列と同様に「順序を考えて」数える」と、24通り
$ _{4}\mathrm{P}_{3}=4\times3\times2=24
2. 「重複して数えてしまった分(重複度)で割り算する」
重複した分は3つの文字の置換の総数
3つの文字の並べ方は$ _{3}\mathrm{P}_{3}=3\times2\times1=6
したがって
$ \frac{_{4}\mathrm{P}_{3}}{_{3}\mathrm{P}_{3}}=\frac{24}{6}=4
したがって組み合わせの計算は
$ _{n}\mathrm{C}_{m}=\frac{_{n}\mathrm{P}_{m}}{_{m}\mathrm{P}_{m}}
さーて戻ってきた。
では、集合の部分集合の数をどう表すかの問題だ
1,1
1,2,1
1,3,3,1
この数をうまく足す方法があれば良い
nとn+1を…こう…上手く使って…cFQ2f7LRuLYP.icon
n個の要素から、0〜n個選ぶ組み合わせの総数はどうなるか？
0個選ぶってなんだ…？cFQ2f7LRuLYP.icon
1. n個から0個選ぶ場合
$ _n\mathrm{C}_{0}？
こんなことできるんか？
$ _{n}\mathrm{P}_{m}=n\times(n-1)\times\cdots\times(n-m+1)
なのでm=0なら
$ \sout{_{n}\mathrm{P}_{0}=n\times(n-0+1)=n(n+1)}
ここに誤りがあります。色々と方法はありますが、次のように考えてみましょうhatori.icon
$ {}_{n}\mathrm{P}_{m}=n\times(n-1)\times\cdots\times(n-m+1)=\frac{n!}{(n-m)!}
したがって$ {}_{n}\mathrm{P}_{0}=\frac{n!}{n!}=1
ついでながら書いておくと、$ 0!=1に注意して$ {}_{n}\mathrm{C}_{m}=\frac{{}_{n}\mathrm{P}_{m}}{{}_{m}\mathrm{P}_{m}}=\frac{n!}{m!(n-m)!}となります
あざます！cFQ2f7LRuLYP.icon
帰ったらなぜズレたのか考えます！
階乗は1*2*3を3!で表すという乃木わかる程度にわかる 誰？
$ _{m}\mathrm{P}_{m}=m\times(m-m+1)=m
なのでm=0なら0通り…？
$ _{n}\mathrm{C}_{0}=\frac{_{n}\mathrm{P}_{0}}{_{0}\mathrm{P}_{0}}=\frac{n(n+1)}{0}=?
計算をミスしてはいないか？
何も選ばない場合(「ば」、「い」がややこしい)
要素は1つもないので空集合になる
2. n個から1個えらぶ
sum関数みたいなことをやりたいのだがうーむ
これはあれだ、$ \Sigmaだ
総和ってどうやったっけな……
数列の和を表すのには$ \sumを使う
数列$ (a_1, a_2, a_3,\cdots)について，第$ p項から第$ q項までの和$ a_p+a_{p+1}\cdots+a_qのことを(ただし$ p, qは整数で，$ p\leq qとする)，
$ \sum_{n=p}^qa_n
と書く。(定義)
総和ルートだと数列に落とし込まないといけない
n-1個とn個だとどう表現するのか
いまここ
恐らく"サブクエスト"に時間がかかりすぎるのは不本意だと思うので、なるべくcFQ2f7LRuLYP.iconさんのやろうとしている方法に従いつつ解答(の一歩手前)を考えてみましたhatori.icon
（注意：これが唯一の証明方法あるいは最も簡単な証明方法というわけではありません。たぶん）
用語の定義１：与えられた集合$ Aの部分集合全体を$ \mathfrak{P}(A)と表し、$ Aの冪集合と呼ぶ $ \mathfrak{P}(A)は集合の集合です
$ \mathfrak{P}はPower setの頭文字Pのフラクトゥール 用語の定義２：有限集合$ Aの要素の個数を$ |A|と表す（無限集合の場合は要素の個数ではなく濃度という） $ \#Aや$ \mathrm{card}(A)とも表す
用語の定義３：集合$ Aと$ Bが共通部分を持たないとき、和集合$ A\cup Bを$ Aと$ Bの(集合論的)直和あるいは非交和とよぶ（このとき特に記号を変えて$ A\sqcup Bとも書く） いま$ X_{3}=\{1,2,3\}とおき、$ |\mathfrak{P}(X_{3})|=2^{3}となることを示します
$ |A|=0の場合：$ A = \emptyset
3つの相異なるものから何も選ばない方法は$ {}_{3}\mathrm{C}_{0}通り
よって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=0\}|={}_{3}\mathrm{C}_{0}
$ |A|=1の場合：$ A \in \{\{1\},\{2\},\{3\}\}
3つの相異なるものから1つのものを選ぶ方法は$ {}_{3}\mathrm{C}_{1}通り
よって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=1\}|={}_{3}\mathrm{C}_{1}
$ |A|=2の場合：$ A \in \{\{1,2\},\{2,3\},\{1,3\}\}
3つの相異なるものから2つのものを選ぶ方法は$ {}_{3}\mathrm{C}_{2}通り
よって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=2\}|={}_{3}\mathrm{C}_{2}
$ |A|=3の場合：$ A =\{1,2,3\}
3つの相異なるものから3つのものを選ぶ方法は$ {}_{3}\mathrm{C}_{3}通り
よって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=3\}|={}_{3}\mathrm{C}_{3}
したがって（一般の$ nに対して書く際は分解を具体的に書かなくても良いですが、今は例を扱っているため丁寧に書くと）
$ \begin{aligned}\mathfrak{P}(X_{3})&=\{\emptyset\}\sqcup \{\{1\},\{2\},\{3\}\} \sqcup \{\{1,2\},\{2,3\},\{1,3\}\} \sqcup \{\{1,2,3\}\} \\ &=\bigsqcup_{m=0}^{3}\{A\in\mathfrak{P}(X_{3}) ; |A|=m\}\end{aligned}
となり（$ |A\sqcup B|=|A|+|B|に注意して）
$ |\mathfrak{P}(X_{3})|=\sum_{m=0}^{3}|\{A\in\mathfrak{P}(X_{3}) ; |A|=m\}|=\sum_{m=0}^{3}{}_{3}\mathrm{C}_{m}
を得ます。最後の和は二項定理の具体例$ \sum_{m=0}^{3}{}_{3}\mathrm{C}_{m}x^{m}=(1+x)^{3}で$ x=1とおけば$ 2^{3}になることが分かります 以上の例における$ 3を$ nに変えて全体を良い感じに書き直すと、一般の場合の証明になります
ありがとうございますcFQ2f7LRuLYP.icon
これは…………どうしたものかな
思ってたよりも相当レベルの高い地帯に迷い込んでたのに気づいたときの気持ち
これ単体で読解しないとどうにもならん
見た目/言葉遣いが仰々しいのでぎょっとされたかもしれませんね...hatori.icon
とはいえ、日常的な言葉というか口語で説明されていたことを数学語(?)に書き直しただけなので、噛み砕けばそんなに高尚なことはしていないはず ネタバレが生えてきた！cFQ2f7LRuLYP.icon
解けるまで見ないぞ
まあ和の計算はメインテーマではない気もしますが…yosider.icon
sore ha soudesu...cFQ2f7LRuLYP.icon
table:n=1
はいる はいらない
1 {}
1 {1}
table:n=2
はいる はいらない
1,2 {}
1 2 {1}
2 1 {2}
1,2 {1,2}
要素が一つ増えるたびに組み合わせが×2通りになる、なので$ 2^nになる？cFQ2f7LRuLYP.icon
言葉が足りない感じ